package algorithm.color2w.algorithm.tree;

import javax.swing.tree.TreeNode;
import java.util.Arrays;
import java.util.List;

/**
 * @author wjl <br/>
 * @version 1.0
 * @ClassName: ReConstructBinaryTree <br/>
 * @Description:
 * 根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
 * <br />
 * @date: 2020/1/2 15:28<br/>
 */
public class ReConstructBinaryTree {
    public static void main(String[] args) {
        int pre[] = {1,2,4,7,3,5,6,8};
        int in[] = {4,7,2,1,5,3,8,6};
        TreeNode a = reConstructBinaryTree(pre, in);
        System.out.println("-- "+a);
    }

//    Definition for binary tree
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /*
        参数为先序遍历和中序遍历的数组
        先序遍历的第一个节点是根节点，拿着个根节点去中序遍历的数组中进行划分，并递归
        问题1. 左右子树所对应的数组如何表示出来
            2.  如何在中序遍历的数组中找到先序中的元素
            3.  如何把pre中要递归的子片段和in中对应上
     */
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        return childTree(pre,in,0,pre.length-1,0,in.length-1);
    }

/*        int pre[] = {1,2,4,7,3,5,6,8};
        int in[] = {4,7,2,1,5,3,8,6};
        inR,preR的初始值，preR起到的作用
*/

    public static TreeNode childTree(int[] pre, int[] in, int inL, int inR, int preL,int preR) {
        if (preL > preR || inL > inR){
            return null;
        }
        TreeNode rootNode = new TreeNode(pre[preL]);
        for(int i = inL; i <= inR; i++){
            if (pre[preL] == in[i]){
                int index = i;
                //偏移量是in中的偏移量
//                int offset = index-preL;
                int offset = index-inL;
//              root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
//              root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                rootNode.left = childTree(pre,in,inL,index-1,preL+1,preL+offset);
                rootNode.right = childTree(pre,in,index+1,inR,preL+offset+1,preR);
                break;
            }
        }
        return rootNode;
    }

//    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
//        return root;
//    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

        if(startPre>endPre||startIn>endIn){
            return null;
        }
        TreeNode root=new TreeNode(pre[startPre]);

        for(int i=startIn;i<=endIn;i++) {
            if (in[i] == pre[startPre]) {
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            }
        }
        return root;
    }

}
